package myheaptree;

import java.util.Arrays;

public class MyHeapTree {
    private int[] elem = new int[10];
    private int usedSize;

    public void initHeap(int[] array){
        for(int i = 0; i < array.length; i++){
            this.elem[i] = array[i];
            this.usedSize++;
        }
    }

    //新增元素
    public void offer(int val){
        //若数组已满则进行扩容
        if(isFull()){
            this.elem = Arrays.copyOf(this.elem, this.elem.length * 2);
        }
        elem[usedSize] = val;
        usedSize++;
        shiftUp(usedSize);
    }

    //删除元素
    public int poll(){
        //记录堆顶元素
        int tmp = elem[0];
        //将对顶元素与最后一个元素进行交换
        swap(0, usedSize-1);
        usedSize--;
        //将堆顶元素进行向下调整
        shifDown(0, usedSize);
        return tmp;
    }

    //以向下调整的方式创建大根堆
    public void createHeap(){
        for(int parent =(usedSize-1-1) / 2; parent >= 0; parent--){
            shifDown(parent,usedSize);
        }
    }
    //向下调整
    private void shifDown(int parent, int useSize) {
        //先找到左孩子，因为双亲不一定有右孩子
        int children = parent * 2 + 1;
        while(children < useSize){
            //使children指向值最大的孩子
            if(children+1 < useSize && elem[children] < elem[children+1]){
                children++;
            }
            if(elem[children] > elem[parent]){
                swap(children,parent);
                parent = children;
                children = children * 2 +1;
            } else {
                break;
            }
        }
    }
    //向上调整
    public void shiftUp(int usedSize){
        int child = usedSize - 1;
        int parent = (child - 1) / 2;
        while(parent >= 0){
            if(elem[child] > elem[parent]){
                swap(child,parent);
                child = parent;
                parent = (parent - 1) / 2;
            } else {
                break;
            }
        }
    }

    private boolean isFull() {
        return this.usedSize == this.elem.length;
    }

    private void swap(int i ,int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }
}
